package main

import "fmt"

/*
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]
*/

/*
根据题目条件生成一颗树，并对这颗树生枝叶的条件按照题目进行限制。

需要左右括号都大于0个时才可以进行生成树的操作（等于0的特殊情况）
生成树之后生出左节点的条件：左括号的剩余数量大于0
生成树之后生成右节点条件：左括号的剩余数量 小于 右括号的剩余数量
当左右括号都为0时，为成功出口，此时进行结算，保存结果。
*/

func generateParenthesis(n int) []string {
	var res []string
	var generate func(left int, right int, n int, s string)
	//curStr	 当前递归得到的结果
	//leftNum	 剩余的左括号个数
	//rightNum   剩余的右括号个数
	generate = func(left int, right int, n int, s string) {
		if left == n && right == n {
			res = append(res, s)
		}
		if left < n {
			generate(left+1, right, n, s+"(")
		}
		if right < left {
			generate(left, right+1, n, s+")")
		}
	}
	generate(0, 0, n, "")
	return res
}

func main() {
	fmt.Println(generateParenthesis(2))
}
